package com.zjsru.oneDay202203;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: likew
 * @Date: 2022/3/14
 *
 * 两个列表的最小索引总和
 *
 * 输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
 * 输出: ["Shogun"]
 * 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
 *
 * 输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
 * 输出: ["Shogun"]
 * 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
 *
 */
public class findRestaurant {
    /*如果 list2[i] 不在哈希表中，跳过：
      如果 list2[i] 在哈希表中：
        索引之和等于 min，将 list2[i] 加入 list；
        索引之和小于 min，更新 min，清空 list，将 list2[i] 加入 ans；
        索引之和大于 min，跳过。
    */
    public String[] findRestaurant(String[] list1, String[] list2) {
        int n = list1.length,m = list2.length;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(list1[i],i);
        }
        List<String> list = new ArrayList<>();
        int min = 3000;
        for (int i = 0; i < m; i++) {
            String s = list2[i];
            if (!map.containsKey(s)){
                continue;
            }
            if (i + map.get(s)<min){
                list.clear();
                list.add(s);
                min = i+ map.get(s);
            }else if(i + map.get(s)==min){
                list.add(s);
            }
        }
        return list.toArray(new String[list.size()]);
    }
    
    public static void main(String[] args) {
        findRestaurant findRestaurant = new findRestaurant();
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
        System.out.println(findRestaurant.findRestaurant(list1, list2));
    }
}
